package tree;
import java.util.*;
public class Ex208 {

    class Trie {

        private boolean isEnd;
        private Trie[] nexts;
        /** Initialize your data structure here. */
        public Trie() {
            nexts = new Trie[26];
            isEnd = false; //默认为false，可以不写
        }
        
        /** Inserts a word into the trie. */
        public void insert(String word) {
            Trie cur = this;
            for (char c: word.toCharArray()) {
                if (cur.nexts[c - 'a'] == null) {
                    //为空时才创建节点，防止重复创建
                    cur.nexts[c - 'a'] = new Trie();
                }
                cur = cur.nexts[c - 'a'];
            }
            cur.isEnd = true;
        }
        
        /** Returns if the word is in the trie. */
        public boolean search(String word) {
            Trie cur = this;
            for (char c : word.toCharArray()) {
                //路径上没有这个字符，说明这个单词不存在
                if (cur.nexts[c - 'a'] == null) return false;
                cur = cur.nexts[c - 'a'];
            }
            //因为是完整的单词，因此需要为true
            return cur.isEnd;
        }
        
        /** Returns if there is any word in the trie that starts with the given prefix. */
        public boolean startsWith(String prefix) {
            Trie cur = this;
            for (char c : prefix.toCharArray()) {
                //和search同样的道理
                if (cur.nexts[c - 'a'] == null) return false;
                cur = cur.nexts[c - 'a'];
            }
            return true; //只是查询一个前缀，不能保证这个前缀是一个实际的单词，如测试用例中的app刚开始就不是存在的
        }
    }
    
    /**
     * Your Trie object will be instantiated and called as such:
     * Trie obj = new Trie();
     * obj.insert(word);
     * boolean param_2 = obj.search(word);
     * boolean param_3 = obj.startsWith(prefix);
     */
    class Trie1{

        private Set<String> set;
        private Map<Character, Set<String>> map;
        /** Initialize your data structure here. */
        public Trie1() {
            set = new HashSet<>();
            map = new HashMap<>();
        }
        
        /** Inserts a word into the trie. */
        public void insert(String word) {
            set.add(word);
            char c = word.charAt(0);
            if (map.containsKey(c)) {
                Set<String> s = map.get(c);
                s.add(word);
                map.put(c, s);
            }
        }
        
        /** Returns if the word is in the trie. */
        public boolean search(String word) {
            return set.contains(word);
        }
        
        /** Returns if there is any word in the trie that starts with the given prefix. */
        public boolean startsWith(String prefix) {
            char c = prefix.charAt(0);
            Set<String> s = map.get(c);
            if (s == null) return false;
            for (String str : s) {
                for (int i = 0; i < prefix.length(); i++) {
                    if (str.charAt(i) != prefix.charAt(i)) return false;
                }
            }
            return true;
        }
    }
    
    /**
     * Your Trie object will be instantiated and called as such:
     * Trie obj = new Trie();
     * obj.insert(word);
     * boolean param_2 = obj.search(word);
     * boolean param_3 = obj.startsWith(prefix);
     */


}
